#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define ForD(i,j,k) for(int i=(j);i>=(k);i--)
#define int long long
using namespace std;
bool Mbe;
const int inf=1e18;
int c;
namespace BF{
    const int N=11;
    #define pii pair<int,int>
    pii edge[N];
    int x[N],y[N],k=0;
    int dis[6][6];
    void solve(){
        k=0;
        int n,m; cin>>n>>m;
        For(i,1,m) cin>>x[i]>>y[i];
        For(i,1,n) For(j,i+1,n) edge[++k]={i,j};
        int ans=inf,cnt=0;
        For(S,0,(1<<k)-1) if(__builtin_popcount(S)==m-1){
            For(i,1,n) For(j,1,n) dis[i][j]=inf;
            For(i,1,n) dis[i][i]=0;
            For(i,1,k) if(S>>(i-1)&1) dis[edge[i].first][edge[i].second]=dis[edge[i].second][edge[i].first]=1;
            For(k,1,n) For(i,1,n) For(j,1,n) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            int res=0;
            For(i,1,m) res+=dis[x[i]][y[i]];
            if(res<ans){
                ans=res;
                cnt=0;
            }
            if(res==ans) cnt++;
        }
        cout<<-ans<<' '<<cnt<<endl;
        return;
    }
}
void solve(){
    if(c>=1&&c<=2) BF::solve();
}
bool Med;
signed main(){
    fprintf(stderr,"%.3lf MB\n",(&Mbe-&Med)/1048576.0);
    freopen("oi.in","r",stdin), freopen("oi.out","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);
    int _=1;
    cin>>c>>_;
    while(_--) solve();
    cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
    return 0;
}